I. Field of the Invention
The present invention relates to digital networks. In particular the invention relates to the interconnection of digital networks.
II. Description of the Related Art
In recent years, digital network systems have been rapidly evolving and becoming increasingly prevalent. For example, the number of digital wireless telephone systems has grown tremendously in both rural areas and large cities. In addition to the standard 900 MHz cellular telephone systems, personal communication systems which operate at 1.8 GHz are also emerging in the larger markets. Personal communication systems are scheduled for continued deployment in smaller markets.
In less developed areas, wireless local loop systems are emerging as a substitute for wireline systems. Wireless local loop systems have certain advantages over wireline systems. In order to provide wireline service, actual copper wire must be installed and connected to each building in which service is provided. The process of laying wire often entails the destruction of existing roads or the installation of a great number of telephone poles. Such installation procedures are invasive to the existing infrastructure, time consuming and expensive. In contrast, in a wireless local loop system, service can be provided to a wide area with the installation of a single base station.
Wireless private branch exchange (PBX) systems are also becoming more prevalent. A wireless PBX system can provide coverage to a related group of users. For example, wireless PBX systems are used in large office buildings. A wireless PBX user may travel throughout the coverage area (i.e., the office building) with his telephone set. The users of a wireless PBX system may contact each other by dialing an extension rather than a full public branch exchange number.
In addition to the increased prevalence of cellular systems, new uses for cellular systems have also developed. For example, data services are commonly provided over existing cellular systems. Data services include data transfer between computers, wireless meter reading, paging services and mobile news service.
Each of the cellular systems discussed above has the characteristic that it is comprised of a plurality of spaced apart base stations. In the most general embodiment, base stations are physically located in the center of a corresponding coverage area. The coverage areas abut one another to form a large, contiguous service area. The base station may use one of a variety of existing or later developed communication techniques to communicate with remote units located within its coverage area. For example, the base station may communicate with the remote units using frequency modulation (FM), time division multiple access (TDMA), a combination of TDMA and frequency hopping (such as GSM) or code division multiple access (CDMA). The use of CDMA provides many advantages to the system such as un-interrupted handoff between base stations, immunity to fading and very high system capacity. Therefore, the following information is disclosed with reference to a CDMA system. However, the generic principles described herein are directly applicable to non-CDMA systems and also non-cellular systems in which digital networks are interconnected.
FIG. 1 shows a block diagram of a typical CDMA Cellular Land Network (CCLN). FIG. 1 shows seven base stations 10A-10G. Each one of the base stations 10A-10G defines a corresponding hexagonal coverage area 12A-12G in which it provides service. Although only seven base stations are shown in FIG. 1, in reality most CCLNs comprise a much greater number of base stations.
Assume a remote unit initiates a communication link with a land line telephone from within the coverage area 12F. The remote unit sends an access message to the base station 10F. The base station 10F transfers the message to a base station controller (BSC) 26. The BSC 26 verifies the authenticity of the remote unit, initiates the billing process and allocates resources within the base station 10F and other portions of the system to be used during the call. This process requires the transfer of more than thirty (30) messages throughout the system. An understanding of the precise nature of these transactions is not fundamental to the present invention.
Instead, of greater importance to us is that, even before a communications link is established between the remote unit and the public switch telephone network, a great number of messages must be transferred between remotely located digital equipment units.
The transfer of messages is facilitated by the use of a CDMA interconnect subsystem (CIS) 20. The CIS 20 is comprised of one or more distribution/consolidation (DISCO) units such as a DISCO 22 shown in FIG. 1. The DISCO 22 is a router, which receives input from a plurality of input ports, consolidates the inputs onto an internal bus. A series of output ports are connected to the internal bus. Each output port has an associated address range. Each message on the internal bus is distributed to the output port which has an address range which includes the address of the message.
Returning to the example above, when the remote unit sends an access message to the base station 10F, the base station 10F creates a message (which may comprise a series of message packets) having an address indicating a control unit within the BSC 26. The base station lo places the message on a corresponding wireline link 14F. The wireline link 14F conveys the message to an input port on the DISCO 22. Within the DISCO 22, a comparison of the address of the message is made with the address ranges of the output port of the DISCO 22. The message has an address within the address filter range associated with a link 28 and, thus, the DISCO 22 routes the message to the BSC 26.
When the BSC 26 allocates resources to be used during the communication with the remote unit, it must designate a cellular modem. The selector bank subsystem (SBS) 30 is comprised of a bank of cellular modems 32A-32X. The BSC 26 sends a message through the DISCO 22 to alert the cellular modem 32A of the connection. The BSC 26 also sends a message to the base station 10F giving the address of the cellular modem 32A.
During the connection, for each frame received from the remote unit over the wireless link, the base station 10F sends a packet of data through the DISCO 22 to the cellular modem 32A. Also, during the connection, the cellular modem 32A sends frames of data intended for the remote unit through the DISCO 22 to the base station 10F.
In this example, let us assume that the remote unit is a cellular portable telephone. The remote unit may change location during the course of the connection. A typical CDMA system employs soft handoff which allows uninterrupted connection during the handoff process from one base station to another. For example, if the remote unit moves from the coverage area 12F to the coverage area 12E, it establishes a connection with the base station 10E before the connection with the base station 10F is released. When the remote unit is simultaneously communicating with the base station 12E and the base station 12F, it is said to be in soft handoff. During soft handoff, the frames emanating from the remote unit are received by both the base station 10E and the base station 10F and forwarded to the DISCO 22 via the link 14E and the link 14F respectfully. The DISCO 22 routes both packet streams to the cellular modem 32A which creates one stream of data to pass to a switch 40.
A CCLN such as the one shown in FIG. 1 has a rather large but limited capacity. The capacity is limited by a number of practical considerations. For example, the capacity is limited by the number of input ports and output ports which can be supported by a single CIS. The capacity is also limited by the maximum geographic distance over which the links 14A-14G operate. Therefore, a large city is typically comprised of more than one CCLN.
Therefore, as a remote unit moves about in a metropolitan area, it may move from the coverage area of one CCLN into the coverage area of a second CCLN. When a communication connection is transferred from a base station associated with a first CCLN to a base station associated with a second CCLN, a number of control messages as well as a number of remote unit data messages must be transferred between the two CCLN systems. Therefore, in order to support a transfer of communication between base stations which are not a part of the same CCLN, a means to effect communication between the CCLNs is necessary.
The CCLNs are connected by the connection of a DISCO in one system with a DISCO of another system. FIG. 1 shows such a connection from the DISCO 22 to/from a DISCO associated with another CCLN. A large address filter 24 passes only those messages having an address corresponding to another CCLN.
FIG. 2 shows a prior art connection configuration with five (5) CCLNs: CCLNA, CCLNB, CCLNC, CCLND, and CCLNE. Note that the number of addresses associated with each CCLN is quite large as each element within each CCLN must have a distinct address. In FIG. 2, each CCLN is directly attached to each other CCLN. Therefore, each of the 5 CCLNs has four address filters. Each of the address filters passes only those packets which are within the range of the corresponding connected CCLN. The problem with the design shown in FIG. 2 is that it impractically increases the size and complexity of the DISCO especially as the number of CCLNs is increased from 5 to a much larger number. Also as the number of address filters increases, the complexity and expense of the interconnection system greatly increases.
FIG. 3 shows another prior art arrangement of five (5) CCLNs. In FIG. 3, each CCLN has only two address filters. In FIG. 3, if CCLNA has a frame for either CCLNB or CCLNC it passes the frame to the CCLNB. The CCLNB transfers frames intended for CCLNA or CCLNE to CCLNA. The problem with the arrangement shown in FIG. 3 is that as the number of CCLNs increases, the delay associated with transferring information around the loop increases. Also, as the number of CCLNs increases, the amount of CCLN processing resources expended to pass through data reaches impractical limits. Another large disadvantage is that the loop configuration is not robust in the presence of failures. If one of the filters fails, a frame of data may begin an endless journey around the loop. In this case, system resources are unnecessarily consumed. If a great number of frames are making an endless journey around the loop, the entire system may become overloaded and fail.
In general, in any system which comprises loops, any single packet of data may traverse two different paths on its journey to the destination node. Obviously any packet which traverses the network over two paths unnecessarily consumes system resources.
In both FIGS. 1 and 2, the address filters play a significant role in determining the complexity and the efficiency of the system. In prior art base stations, the address filters may comprise large look-up tables. As each packet enters the filter, the filter compares the address in the address header to entries in the table. If a match is found, the filter passes the packet through the filter. Such a filter requires a large amount of memory and circuitry. Operation of such a system requires a significant amount of processing time for each packet. Therefore, in a large system with many addresses, the filtering process consumes large amounts of the system resources and can add significant delay to the journey of a packet.
Thus, it will be appreciated that there is a need in the industry for a means and method of interconnecting nodes on a large digital system which overcomes the complexities and shortcomings of the prior art. The present invention provides a simple and efficient means and method for interconnecting such devices.
When a large digital network is interconnected with a multiplicity of other large digital networks, an efficient logical topology and a corresponding address assignment must be determined. According to the invention, a network is determined which has a tree topology in which the addresses associated with each branch of the tree are a contiguous set of numbers or the converse of a contiguous set. Each branch of the system uses only one simple logical address filter to determine packets which pass through the filter. The invention provides means of determining an address assignment for a general network given a number of design parameters.
The invention offers several advantages over prior art systems. One of the advantages is that each node on the tree has a path to each other node. Therefore, no portion of the network is disconnected with any other portion. Another advantage is that the topology eliminates the need to broadcast packets. When a node broadcasts a packet, the packet is transmitted from the transmitting node to every other node in the system. Broadcasting consumes a substantial amount of network resources.
Avoiding the use of broadcast signals greatly increases the efficiency of the present design.
Yet another advantage is that the topology of the invention does not comprise loops. If the system comprises loops, any single packet of data may traverse two different paths on its journey to the destination node. In this case, system resources are unnecessarily consumed.
Also, in the invention, all addresses that may pass into or out of a port on a node have contiguous addresses or are the logical converse of a contiguous set of addresses. The advantage of contiguous addresses is that a single, simple logical address filter can be used at each port. The concept of contiguous addresses and the advantages gained by their use shall be more clear when taken in conjunction with the discussion below.
The invention is a novel and improved logical topology and corresponding address assignment system for interconnecting large digital networks and a means for determining such an assignment. According to the invention, addresses are assigned to a set of nodes in a tree topology such that a single filter using a single simple logical operation connects each branch of the tree.
According to the invention, a system is designed which has a tree topology in which the addresses associated with each branch of the tree are a contiguous set or the converse of a contiguous set of numbers. Each branch of the system uses only one address filter to determine packets which pass through the filter. The address filter is a simple logical function which can be implemented with a small amount of circuitry.
According to the invention, the nodes are arranged in a tree topology in which each node is connected to each other node by a single path. Next, an ordered list of the nodes is generated. In order to generate the list, one node is designated a root node and is recorded on the list. The flow now enters any node connected to the root node which does not yet have an entry on the list. The second node is recorded. The flow continues to enter subsequent unrecorded nodes while sequentially recording each node on the list. When the flow arrives at a node to which no unrecorded node is connected, the flow retreats one node closer to the root node without recording an entry on the list. If unrecorded nodes are connected to the node, the flow continues as above. If each of the connected nodes has a corresponding entry on the list, the flow retreats again. Flow continues in this manner until all the nodes of the system have been recorded. Once recorded, each node is assigned a number of sequential address blocks according the list.